package BinaryTree;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author shy_black
 * @date 2019/3/17 13:54
 * @Description:二叉树的基本操作法
 */
public class LinkedBinaryTreeImpl implements IBinaryTree {
    private Node root;

    public LinkedBinaryTreeImpl(Node root) {
        this.root = root;
    }

    @Override
    public boolean isEmpty() {

        return root == null;
    }

    @Override
    public int size() {
        System.out.print("二叉树节点的个数:");
        return this.size(root);
    }

    private int size(Node root) {
        if (root == null) {
            return 0;
        } else {
            //遍历左子树
            int n1 = this.size(root.leftChild);
            //遍历右子树
            int n2 = this.size(root.rightChild);
            //相加在加有头节点
            return n1 + n2 + 1;
        }
    }

    @Override
    public int getHeight() {
        System.out.print("二叉树的高度==");
        return this.getHeight(root);
    }

    private int getHeight(Node root) {
        if (root == null) {
            return 0;
        } else {
            //获取左子树高度
            int n1 = this.getHeight(root.leftChild);
            //获取右子树高度
            int n2 = this.getHeight(root.rightChild);

            // 返回左，右子树较大高度并加1
            return n1 > n2 ? n1 + 1 : n2 + 1;
        }
    }

    @Override
    public Node findKey(Object value) {
        System.out.println("查找值为" + value + ",结果为：");
        return findKey(value, root);
    }

    private Node findKey(Object value, Node root) {
        //查找双亲节点是否为value值的节点
        if (root == null) {
            return null;
        } else if (root != null && root.value == value) {
            return root;
        } else {
            //查找叶子节点是否为value节点
            Node node1 = this.findKey(value, root.leftChild);
            Node node2 = this.findKey(value, root.rightChild);
            if (node1 != null && node1.value == value) {
                return node1;
            } else if (node2 != null && node2.value == value) {
                return node2;
            } else {
                return null;
            }

        }
    }

    @Override
    public void preOrderTraverse() {
        //输出根节点值
        if (root != null) {
            System.out.print(root.value + "--");
            //对左子树先序遍历
            //构建一个二叉树，根是左子树的根
            IBinaryTree leftTree = new LinkedBinaryTreeImpl(root.leftChild);
            leftTree.preOrderTraverse();
            //对右子树先序遍历
            //构建一个二叉树，根是左子树的根
            IBinaryTree rightTree = new LinkedBinaryTreeImpl(root.rightChild);
            rightTree.preOrderTraverse();
        }
    }

    @Override
    public void midOrderTraverse() {
        System.out.println("中序遍历开始。。。");
        this.midOrderTraverse(root);
        System.out.println();
    }

    private void midOrderTraverse(Node root) {
        if (root != null) {
            //遍历左子树
            this.midOrderTraverse(root.leftChild);
            //输出根的值
            System.out.print(root.value + "--");
            //遍历右子树
            this.midOrderTraverse(root.rightChild);
        }
    }

    @Override
    public void postOrderTraverse() {
        System.out.println("后序遍历开始。。。");
        this.postOrderTraverse(root);
        System.out.println();
    }

    private void postOrderTraverse(Node root) {
        if (root != null) {
            //遍历左子树
            this.postOrderTraverse(root.leftChild);
            //遍历右子树
            this.postOrderTraverse(root.rightChild);
            //输出根
            System.out.print(root.value + "--");
        }
    }

    @Override
    public void preOrderByStack() {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (stack != null) {
            Node cur = stack.pop();
            System.out.println(cur.value);
            if (cur.rightChild != null) {
                stack.push(cur.rightChild);
            }
            if (cur.leftChild != null) {
                stack.push(cur.leftChild);
            }
        }
    }
    //使用一个实现栈，一个辅助栈，每次实现栈出栈时，都入栈到辅助栈中
    //当遍历结束后，节点从辅助栈中出栈，即可得到后序遍历
    @Override
    public void postOrderByStack() {
        System.out.println("非递归后序遍历---");
        Deque<Node> s1 = new LinkedList<>();
        Deque<Node> s2 = new LinkedList<>();
        s1.push(root);
        Node temp = root;
        while (!s1.isEmpty()) {
            Node cur = s1.pop();
            s2.push(cur);

            if (cur.leftChild != null)
                s1.push(cur.leftChild);
            if (cur.rightChild != null)
                s1.push(cur.rightChild);
        }
        while(!s2.isEmpty()) {
            System.out.println(s2.pop().value+"--");
        }
    }

    @Override
    public void midOrderByStack() {
        System.out.println("非递归中序遍历---");
        Deque<Node> stack = new LinkedList<Node>();
        Node current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.leftChild;
            }
            if (!stack.isEmpty()) {
                current = stack.pop();
                System.out.print(current.value + "--");
                //进入右子树，开始新的一轮左子树遍历(这是递归的自我实现)
                current = current.rightChild;
            }
        }
        System.out.println();
    }

    @Override
    public void levelOrderbyStack() {
        System.out.println("按照层次遍历二叉树---");
        if (root == null) return;
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while (queue.size() != 0) {
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                Node temp = queue.poll();
                System.out.println(temp.value + "--");
                if (temp.leftChild != null)
                    queue.add(temp.leftChild);
                if (temp.rightChild != null)
                    queue.add(temp.rightChild);
            }
        }
    }
}
